Variations

0/1 knapsack problem

TODO: Describe the dynamic programming approach TODO: Describe the meet-in-the-middle approach

Bounded knapsack problem

TODO: Describe $O(\log W)$ reduction from bounded knapsack to 0/1 knapsack (only works when optimizing?) ¹²

Unbounded knapsack problem

Unbounded knapsack can be reduced to 0/1 knapsack in a similar manner as bounded knapsack

Fractional knapsack problem

TODO: Describe greedy algorithm

Problems

• Knapsack
• Walrus Weights
• Roller coaster fun
• Tug of War
• Buffed Buffet
• Lucky Country³

See also

• NP-complete
• Frobenius coin problem

External links

• Continuous knapsack problem